# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/11/3
# @File : 31.(数位DP01）Amount of Degrees（度的数量）.py
# https://loj.ac/p/10163
# https://www.bilibili.com/video/BV1yT4y1u7jW?spm_id_from=333.999.0.0
# https://blog.csdn.net/HangHug_L/article/details/114493203
# 这题注意取某个数和是某个数是不一样的。
N = 32
def dp_solve(n):
    dp = []
    while(n):
        dp.append(n%b)#存储B进制数的各位
        n = n // b
    res = 0#统计方案数
    last = 0#统计已经有多少个1
    for i in range(len(dp)-1,-1,-1):
        x = dp[i]#从最高位开始
        if(x>=1):
            res += C[i][k-last]#枚举取0的情况
            if(x>1):
                if(k-last-1>=0):res += C[i][k-last-1]#枚举取1的情况
                break# 计数就已经结束了。因为这一位是已经大于1，后面的位不用再数了。
            else:#这一位就是1时，可以往后面的位走了
                last += 1
                if(last>k):break# 此时路径上的1已经大于要求，不用再继续往后面的位找
        if(i==0 and k == last):#可以一直走到最后也是一种情况。
            res += 1
    return res

"""
数位DP中一般会这样问：某一区间内满足某种性质的一类数.
1,f ( x , y ) = > f [ y ] − f [ x − 1 ] 类似前缀和
2，从树的角度去考虑。

这题是能是取每位0或者1才行。这个数恰好等于K个互不相等的B的整数次幂之和，不然不符合题意。
"""
if __name__ == '__main__':
    x,y = map(int,input().split())
    k = int(input())
    b = int(input())
    C = [[0]*N for _ in range(N)]#预处理求出组合数 c(a,b)=c(a-1,b)+c(a-1,b-1);表示高度为i的完全二叉树的数中二进制恰好有j个1的数的个数(方案数）
    for i in range(N):
        for j in range(0,i+1):#j到i，因为一共才i个，大于i的j要为0；
            if j==0:
                C[i][j]  = 1
            else:
                C[i][j] = C[i-1][j] + C[i-1][j-1]

    ans = dp_solve(y)-dp_solve(x-1)
    print(ans)
